from typing import Counter, List


class Solution:
    def medianOfUniquenessArray(self, nums: List[int]) -> int:
        n = len(nums)
        median = (n * (n+1)//2 + 1)//2
        def check(t):
            cnt = Counter()
            j,tot = 0,0
            for i,v in enumerate(nums):
                cnt[v] += 1
                while len(cnt) > t:
                    cnt[nums[j]] -= 1
                    if cnt[nums[j]] == 0:
                        del cnt[nums[j]]
                    j += 1
                tot += i-j+1
            return tot >= median
        res = 0
        lo,hi = 1,n
        while lo <= hi:
            mid = (lo + hi)//2
            if check(mid):
                res = mid
                hi = mid -1
            else:
                lo = mid + 1
        return res 